1. Field of the Invention
This invention generally relates to computer systems, and more specifically, to detecting and correcting errors in data transmitted from a memory of a computer system.
2. Background Art
The small size of computer transistors and capacitors, combined with transient electrical and electromagnetic phenomena, cause occasional errors in stored information in computer memory systems. Therefore, even well designed and generally reliable memory systems are susceptible to memory device failures.
In an effort to minimize the effects of these memory device failures, various error-checking schemes have been developed to detect, and in some cases correct, errors in messages read from memory. The simplest error detection scheme is the parity bit. A parity bit is an extra bit included with a binary data message or data word to make the total number of 1's in the message either odd or even. For “even parity” systems, the parity bit is set to make the total number of 1's in the message even. For “odd parity” systems, the parity bit is set to make the total number of 1's in the message odd. For example, in a system utilizing odd parity, a message having two 1's would have its parity bit set to 1, thereby making the total number of 1's odd. Then, the message including the parity bit is transmitted and subsequently checked at the receiving end for errors. An error results if the parity of the data bits in the message does not correspond to the parity bit transmitted. As a result, single bit errors can be detected. However, since there is no way to detect which particular bit is in error, correction is not possible. Furthermore, if two or any even number of bits are in error, the parity will be correct and no error will be detected. Parity therefore is capable of detecting only odd numbers of errors and is not capable of correcting any bits determined to be in error.
Error correction codes (ECCs) have thus been developed to not only detect but also correct bits determined to be in error. ECCs utilize multiple parity check bits stored with the data message in memory. Each check bit is a parity bit for a group of bits in the data message. When the message is read from memory, the parity of each group, including the check bit, is evaluated. If the parity is correct for all of the groups, it signifies that no detectable error has occurred. If one or more of the newly generated parity values are incorrect, a unique pattern called syndrome results, which may be used to identify the bit in error. Upon detection of the particular bit in error, the error may be corrected by complementing the erroneous bit.
A widely used type of ECC utilized in error control in digital systems is based on the codes devised by R. W. Hamming, and thus take the name “Hamming codes”. One particular subclass of Hamming codes includes the single error correcting and double error detecting (SEC-DED) codes. As their name suggests, these codes may be utilized not only to correct any single bit error but also to detect double bit errors.
Another type of well-known ECC is the single symbol correction and double symbol detection (SSC-DSD) codes, which are used to correct single symbol errors and detect double symbol errors. In systems implementing these types of codes, the symbol represents a multiple bit package or chip. Hence, as the name implies, an SSC-DSD code in a system utilizing n bit symbols would be capable of correcting n bits in a single symbol and detecting errors occurring in double symbols.
As memory systems become larger, conventional single symbol error correct, double symbol error detect strategies, are no longer adequate. New strategies are required to deal with entire memory chip failures. Typically, several chips are used to hold user data with one or more additional chips used for check information and other required system data. If each cache line had two redundant chips, which could be used entirely for correction, then, for example, a conventional Reed-Solomon error correction strategy could be used. However frequently the system requires that a portion of the extra chips are allocated for system specific information, and the ECC has less than 2 full chips available for holding check information. Examples of such information are those that would reduce the power of the memory system, or improve the reliability of the memory system.